`
https://leetcode.cn/problems/unique-binary-search-trees-ii/
`

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function (n) {
  return build(1, n)
};

function build(lo, hi) {
  const res = []

  if (lo > hi) {
    // 这里需要装一个 null 元素，这样才能让下面的两个内层 for 循环都能进入，正确地创建出叶子节点
    res.push(null)
    return res
  }

  // 穷举 root 节点的所有可能
  for (let i = lo; i <= hi; i++) {
    // 递归构造出左右子树的所有有效 BST
    const leftTree = build(lo, i - 1)
    const rightTree = build(i + 1, hi)

    // 给 root 节点穷举所有左右子树的组合
    for (const left of leftTree) {
      for (const right of rightTree) {
        // i 作为根节点 root 的值
        const root = new TreeNode(i)
        // 把递归构造出的左右子树挂到 root 节点上
        root.left = left
        root.right = right
        res.push(root)
      }
    }
  }

  return res
}

generateTrees(3)
